package org.jspar.partition;

import java.util.ArrayList;
import java.util.List;

import org.jspar.Options;
import org.jspar.Partition;
import org.jspar.matrix.ConnectionMatrix;
import org.jspar.model.Module;
import org.jspar.model.NetList;

public class Partitioning {

	private PartitionRule partitionRule;
	private ConnectionMatrix matrix;

	private List<Cluster> clusters;
	private List<Partition> partitions;
	private List<Cluster> selectedClusters;

	public Partitioning(Options conf,
			ConnectionMatrix matrix, NetList netlist) {
		partitionRule = conf.getPartitionRule();
		this.matrix = new ConnectionMatrix(matrix);
		partitions = new ArrayList<Partition>();
		initClusters(netlist.modules());
	}

	private void initClusters(Module[] modules) {
		clusters = new ArrayList<Cluster>();
		for (int i = 0; i < modules.length; ++i) {
			clusters.add(new Cluster(modules[i], matrix.valueAt(modules[i])));
		}
		selectedClusters = new ArrayList<Cluster>();
	}

	public List<Partition> buildPartitions() {
		while (clusters.size() > 1) {
			if (! findNextClusters()) {
				break;
			}
			mergeClusters();
		}
		
		while (clusters.size() >0)
			selectedClusters.add(clusters.remove(0));

		for (int i = 0; i < selectedClusters.size(); ++i) {
			Cluster c = selectedClusters.get(i);
			if (c.size() > 0)
				partitions.add(new Partition(c.modules()));
		}
		return partitions;
	}

	private int bestI, bestJ;

	private boolean findNextClusters() {
		boolean found = false;
		double best = 0.0;
		for (int i = 0; i < clusters.size(); ++i) {
			for (int j = i+1; j < clusters.size(); ++j) {
				if (matrix.valueAt(i, j) > 0 || matrix.valueAt(j, i) > 0) {
					double v = matrix.connectionRatio(i, j);
					if (! found || v < best) {
						best = v;
						found = true;
						bestI = i;
						bestJ = j;
					}
				}
			}
		}
		return found;
	}

	private void mergeClusters() {
		Cluster i = clusters.get(bestI);
		Cluster j = clusters.get(bestJ);
		int c = matrix.externalConnections(bestI, bestJ);

		if (isAcceptable(i, j, c)) {
			i.mergeWith(j, c);
			clusters.remove(j);
			matrix.merge(bestI, bestJ);
		} else if (i.size() > j.size()) {
			selectedClusters.add(i);
			clusters.remove(i);
			matrix.remove(bestI);
		} else /* if (j.size() > i.size()) */ {
			selectedClusters.add(j);
			clusters.remove(j);
			matrix.remove(bestJ);
		}
	}

	private boolean isAcceptable(Cluster i, Cluster j, int c) {
		return partitionRule.isAcceptable(i, j, c);
	}
}
